#pragma once
#include <iostream>
#include <vector>
#include <algorithm>

namespace my {
	template <class T>
	class priority_queue {
	private:
		std::vector<T> _container;
		typedef std::vector<T> Container;
	public:
		void HeapAdjustUp(size_t child) {
			if (_container.size() > 1) {
				size_t parent = (child - 2) / 2;
				while (child > 0) {
					if (_container[child] < _container[parent]) {
						std::swap(_container[child], _container[parent]);
						HeapAdjustUp(parent);
					}
					else {
						--child;
						parent = (child - 2) / 2;
					}
				}
			}
		}

		void HeapAdjustDown(size_t parent) {
			if (_container.size() > 1) {
				size_t child = parent * 2 + 1;
				while (child < _container.size() && child <= parent * 2 + 2) {
					if (_container[child] < _container[parent]) {
						std::swap(_container[child], _container[parent]);
						HeapAdjustDown(child);
					}
					else
						++child;
				}
			}
		}

		priority_queue(const Container& con = Container()) {
			for (int i = 0; i < con.size(); ++i) {
				_container.push_back(con[i]);
				HeapAdjustUp(_container.size() - 1);
			}
		}

		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last) {
			while (first != last) {
				_container.push_back(*(first++));
				HeapAdjustUp(_container.size() - 1);
			}
		}

		bool empty() const {
			return _container.empty();
		}

		size_t size() const {
			return _container.size();
		}

		const T& top() const {
			return _container.front();
		}

		void push(const T& val) {
			_container.push_back(val);
			HeapAdjustUp(_container.size() - 1);
		}

		void pop() {
			_container[0] = _container[_container.size() - 1];
			_container.pop_back();
			HeapAdjustDown(0);
		}

		void swap(priority_queue& x) {
			_container.swap(x._container);
		}
	};
}